A. Field of the Invention
The present invention relates generally to data processing and data routing and, more particularly, to maintaining packet order within a router.
B. Description of Related Art
Routers receive data on a physical media, such as optical fiber, analyze the data to determine its destination, and output the data on a physical media in accordance with the destination. Routers were initially designed using a general purpose processor executing large software programs. As line rates and traffic volume increased, however, general purpose processors could not scale to meet these new demands. For example, as functionality was added to the software, such as accounting, filtering, and policing functionality, these routers suffered performance degradation. In some instances, the routers failed to handle traffic at line rate when the new functionality was turned on.
To meet the new demands, purpose-built routers were designed. Purpose-built routers are designed and built with components optimized for routing. They not only handled higher line rates and higher network traffic volume, but they also added functionality without compromising line rate performance.
A purpose-built router may include a number of input and output ports from which it transmits and receives information packets. Packets may belong to the same data flow. Generally, packets in the same data flow should be transmitted from the router in the same order they are received by the router. In other words, it is undesirable for the router to reorder packets within a data flow.
In certain purpose-built routers, however, components within the router may have a tendency to reorder packets as the packets are being processed. For example, a router may include multiple route lookup engines executing in parallel and asynchronously with one another. Because the time to perform a route lookup may not be constant, the route lookup engines may finish processing packets in an out-of-order sequence relative to the order in which the engines began processing their packets.
Accordingly, there is a need to ensure that certain packets exit the router in the same order that they entered the router.